/* game of life implementation
 * This file implements Conway's game of life using pthreads and memory optimizations
 * Here is a brief list of optimizations used
 * 1 - The game of life world is divided into horizintal slices for each thread to work on
 * 2 - For each thread, the game of life algorithm is optimized by remembering the states
 *     of the neighbors that will be used in the next iteration and reducing the number of
 *     lookups into the arrays 
 * 3 - To further optimize the time, instead of counting the neighbors and using the alivep()
 *     function, a hash map is used that is indexed by the states of the neightbors. This saves calculation time
 */
#include <stdlib.h>
#include <pthread.h>
#include "life.h"
#include "util.h"

/**
 * Swapping the two boards only involves swapping pointers, not
 * copying values.
 */
#define SWAP_BOARDS( b1, b2 )  do { \
    char* temp = b1; \
    b1 = b2; \
    b2 = temp; \
} while(0)

#define NUM_THREADS     4

// define the data that is passed to the threads.
struct thread_data{
	pthread_barrier_t* barr;
	int tId;
	int gens;
	int LDA;
    int row_start;
    int row_end;
    int col_start;
    int col_end;
	char** outboard;
	char** inboard;
};

/* generate - this is the function that each individual thread works on.
   for each thread, it runs the game of life algorithm on the slice of the array
   that is indicated.
 */
void* generate(void *p) {
    struct thread_data *my_data;
    // get the data that was passed to this thread
    my_data = (struct thread_data *) p;

    // allocate some variables to hold data
    int i, j, inorth, isouth, jeast;
    int row_offset, row_offset_north, row_offset_south;

    // extracting the data from the packet to local variables - this is faster
	pthread_barrier_t* barr = my_data->barr;
	int tId = my_data->tId;
	int gens_max = my_data->gens;
    int row_start = my_data->row_start;
    int row_end = my_data->row_end;
    int col_start = my_data->col_start;
    int col_end = my_data->col_end;
	int LDA = my_data->LDA;

	int curgen;
    int state;

    // run the game of life algorithm for gen_max generations.
	for (curgen = 0; curgen < gens_max; curgen++) {
        //wait until all threads reach this barrier
		pthread_barrier_wait(barr);
        //fetch the source and destination boards
		char* outboard = *(my_data->outboard);
		char* inboard = *(my_data->inboard);

        //allocating memory to hold the state of the neighboring cells
        //the last 9 bits in the state variable represent the states of the neighboring cells like this
        /* state = NW,W,SW,N,C,S,NE,E,SE */
        // initialize the state variable to zero
        state = 0;

        //fetching the states for the NW, W, N and Current cell into the state variable
		state |=
			(inboard[mod(row_start-1,LDA)*LDA+mod(col_start-1,LDA)] << 8) | //NW
			(inboard[row_start*LDA+mod(col_start-1,LDA)] << 7) | //W
			(inboard[mod(row_start-1,LDA)*LDA+col_start] << 5) | //N
			(inboard[row_start*LDA+col_start] << 4); //C

		for (i = row_start; i < row_end; i++) {
            // doing some code motion here to reduce the number of multiplies and just work with offsets
			inorth = mod (i-1, LDA);
			isouth = mod (i+1, LDA);
			row_offset = i*LDA;
			row_offset_north = inorth*LDA;
			row_offset_south = isouth*LDA;

            // fetching the states of the S and SW cells, as this gets updated when go to
            // the next iteration of the 'i' loop
			state |= 
				(inboard[row_offset_south + mod(col_start-1,LDA)] << 6) | //SW
				(inboard[row_offset_south + mod(col_start,LDA)] << 3); //S

			for (j = col_start; j < col_end; j++) {
				//doing the update to the cell block
				jeast = mod (j+1, LDA);

				//determining the state
                // fetching the states of the N, NE, and SE, as this gets updated when go to
                // the next iteration of the 'j' loop
				state |=
					(inboard[row_offset_north + jeast] << 2) | // NE
					(inboard[row_offset + jeast] << 1) | // E
					(inboard[row_offset_south + jeast] << 0); // SE

                // using the state as a hash key to get the state of the Current cell.
				outboard[row_offset + j] = alive_hash (state);

				// copying the cell state from the cell to the east
                // this is done to avoid unnessary memory accesses in the next iteration
                // because that would slow things down unnecessarily, instead we just copy the bits over
                // so that C becomes W, N becomes NW, and so on.
				state = (state << 3) & 0x000001FF;
			}
			//copying the cell from the cell to the south
            // this is done to avoid unnessary memory accesses in the next iteration
            // because that would slow things down unnecessarily, instead we just copy the bits over
            // so that C becomes N, W becomes NW, and so on.
			state = (state << 1) & 0x000001B0;
		}
        // wait until all the threads are done
		pthread_barrier_wait(barr);
        // only one of the threads needs to swap boards.
		if (tId == 0)
			SWAP_BOARDS( *(my_data->outboard), *(my_data->inboard) );
	}

    return NULL;
}

/* the game_of_life optimized implementation
 * it takes the input and output board and runs a parallel and optimized implementation
 * will spawn threads if the board is bigger than 32 by 32. otherwise just runs the regular 
 * sequential implementation on it.
 */
char* game_of_life (char* outboard, 
        char* inboard,
        const int nrows,
        const int ncols,
        const int gens_max) {

    // the board is too small, just do sequential!
	if (nrows < 32)
		return sequential_game_of_life (outboard, inboard, nrows, ncols, gens_max);

    // getting the LDA dimensions, since the board is square, we don't need anything fancy here
	int LDA = nrows;

    int t;
	pthread_barrier_t* barr = malloc(sizeof(pthread_barrier_t));
    pthread_t threads[NUM_THREADS-1];
    struct thread_data data[NUM_THREADS];

    // packing the data into the structure to pass to every thread
    for (t=0; t<NUM_THREADS; t++) {
        data[t].barr = barr;
        data[t].tId = t;
        data[t].gens = gens_max;
        data[t].LDA = LDA;
        data[t].outboard = &outboard;
        data[t].inboard = &inboard;

        // assign slices to each thread by marking the begin and end rows/columns
        // right now we are using horizontal stripes to separate the board.
        data[t].row_start = (t*nrows)/NUM_THREADS;
        data[t].row_end = ((t+1)*nrows)/NUM_THREADS;
        data[t].col_start = 0;
        data[t].col_end = nrows;
    }

    pthread_barrier_init(barr, NULL, NUM_THREADS);

    for(t=0; t<NUM_THREADS-1; t++) { //spawning threads
        pthread_create(&threads[t], NULL, generate, (void *) &(data[t]));
    }

    //main thread doing work
    generate((void *) &(data[t]));

    for(t=0; t<NUM_THREADS-1; t++) {
        pthread_join(threads[t], NULL);
    }

    /* 
     * We return the output board, so that we know which one contains
     * the final result (because we've been swapping boards around).
     * Just be careful when you free() the two boards, so that you don't
     * free the same one twice!!! 
     */
    return outboard;
}
